#include <bits/stdc++.h>

using namespace std;

// 绝对差不超过限制的最长连续子数组
// 给你一个整数数组 nums ，和一个表示限制的整数 limit
// 请你返回最长连续子数组的长度
// 该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit
// 如果不存在满足条件的子数组，则返回 0
// 测试链接 : https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

class Solution 
{
private:
    static const int MAXN = 100001;
    // 窗口内最大值的更新结构（单调队列）
    int maxDeuqe[MAXN];
    // 窗口内最小值的更新结构（单调队列）
    int minDeuqe[MAXN];
    int maxh, maxt, minh, mint;
    vector<int> arr;

	// 判断如果加入数字number，窗口最大值 - 窗口最小值是否依然 <= limit
	// 依然 <= limit，返回true
	// 不再 <= limit，返回false
    bool ok(int limit, int num)
    {
        // mx : 如果number进来，新窗口的最大值
        int mx = maxh < maxt ? max(arr[maxDeuqe[maxh]], num) : num;
        // mn : 如果number进来，新窗口的最小值
        int mn = minh < mint ? min(arr[minDeuqe[minh]], num) : num;
        return mx - mn <= limit;
    }

    // r位置的数字进入窗口，修改窗口内最大值的更新结构、修改窗口内最小值的更新结构
    void push(int r)
    {
        while(maxh < maxt && arr[maxDeuqe[maxt - 1]] <= arr[r]) --maxt;
        maxDeuqe[maxt++] = r; 
        while(minh < mint && arr[minDeuqe[mint - 1]] >= arr[r]) --mint;
        minDeuqe[mint++] = r; 
    }

    // 窗口要吐出l位置的数了！检查过期！
    void pop(int l)
    {
        if(maxh < maxt && maxDeuqe[maxh] == l) ++maxh;
        if(minh < mint && minDeuqe[minh] == l) ++minh;
    }

public:
    int longestSubarray(vector<int>& nums, int limit) 
    {
        maxh = maxt = minh = mint = 0;
        arr = nums;
        int n = nums.size(), ans = 0;
        for(int l = 0, r = 0; l < n; ++l)
        {
            // [l,r)，r永远是没有进入窗口的、下一个数所在的位置
            while(r < n && ok(limit, nums[r])) push(r++);
            // 从while出来的时候，[l,r)是l开头的子数组能向右延伸的最大范围
            ans = max(ans, r - l);
            pop(l);
        }
        return ans;
    }
};



class Solution 
{
public:
    int longestSubarray(vector<int>& nums, int limit) 
    {
        int n = nums.size(), left = 0, right = 0, ret = 0;
        map<int, int> m;
        while(right < n)
        {
            ++m[nums[right]];
            while(m.rbegin()->first - m.begin()->first > limit)
            {
                if(--m[nums[left]] == 0) m.erase(nums[left]);
                ++left;
            }
            ret = max(ret, right - left + 1);
            ++right;
        }
        return ret;
    }
};